/*
 * @lc app=leetcode.cn id=705 lang=javascript
 *
 * [705] 设计哈希集合
 */

// @lc code=start
/**
 * Initialize your data structure here.
 */
var MyHashSet = function (capacity = 4) {
  this.capacity = capacity;
  this.size = 0;
  this.st = new Array(4);
  this.resize = (capacity) => {
    const hash = new MyHashSet(capacity);
    for (let i = 0; i < this.capacity; i++) {
      if (this.st[i] !== void 0) {
        hash.add(this.st[i]);
      }
    }
    this.st = hash.st;
    this.capacity = hash.capacity;
  };
  this.hash = (key) => {
    return key % this.capacity;
  };
};

/**
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.add = function (key) {
  // 扩容hash table
  if (this.size >= this.capacity / 2) {
    this.resize(this.capacity * 2);
  }
  let i;
  for (i = this.hash(key); this.st[i] !== void 0; i = (i + 1) % this.capacity) {
    // 原来有值就更新
    if (this.st[i] === key) {
      this.st[i] = key;
      return;
    }
  }
  this.st[i] = key;
  this.size++;
};

/**
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.remove = function (key) {
  if (!this.contains(key)) return;

  // 找到对应hash
  let i = this.hash(key);
  while (this.st[i] !== key) {
    i = (i + 1) % this.capacity;
  }
  this.st[i] = void 0;
  this.size--;

  // 剩下重复的hash重新排序
  i = (i + 1) % this.capacity;
  while (this.st[i] !== void 0) {
    let key = this.st[i];
    this.st[i] = void 0;
    this.size--;
    this.add(key);
    i = (i + 1) % this.capacity;
  }

  // 收缩hash table
  if (this.size > 0 && this.size < this.capacity / 8) {
    this.resize(this.capacity / 2);
  }
};

/**
 * Returns true if this set contains the specified element
 * @param {number} key
 * @return {boolean}
 */
MyHashSet.prototype.contains = function (key) {
  for (let i = this.hash(key); this.st[i] !== void 0; i = (i + 1) % this.capacity) {
    if (this.st[i] === key) {
      return true;
    }
  }
  return false;
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * var obj = new MyHashSet()
 * obj.add(key)
 * obj.remove(key)
 * var param_3 = obj.contains(key)
 */
// @lc code=end
